The present invention relates to a system and method for applying flexible generation constraints, and in particular, to a system and method for applying such complex constraints to a functional verification programming environment during test generation.
Design verification is the process of determining whether an integrated circuit, board, or system-level architecture, exactly implements the requirements defined by the specification of the architecture for that device. Design verification for a device under testing (DUT) may be performed on the actual device, or on a simulation model of the device. For the purposes of explanation only and without intending to be limiting in any way, the following discussion centers upon testing which is performed on simulation models of the device.
As designs for different types of devices and device architectures become more complex, the likelihood of design errors increases. However, design verification also becomes more difficult and time consuming, as the simulation models of the design of the device also become more complex to prepare and to test.
The problem of design verification is compounded by the lack of widely generalizable tools which are useful for the verification and testing of a wide variety of devices and device architectures. Typical background art verification methods have often been restricted to a particular device having a specific design, such that the steps of preparing and implementing such verification methods for the simulation model must be performed for each new device.
The process of verifying a design through a simulation model of the device is aided by the availability of hardware description languages such as Verilog and VHDL. These languages are designed to describe hardware at higher levels of abstraction than gates or transistors. The resultant simulated model of the device can receive input stimuli in the form of test vectors, which are a string of binary digits applied to the input of a circuit. The simulated model then produces results, which are checked against the expected results for the particular design of the device. However, these languages are typically not designed for actual verification. Therefore, the verification engineer must write additional programming code in order to interface with the models described by these hardware description languages in order to perform design verification of the device.
Examples of testing environments include static and dynamic testing environments. A static testing environment drives pre-computed test vectors into the simulation model of the DUT and/or examines the results after operation of the simulation model. In addition, if the static testing environment is used to examine the results output from the simulation model, then errors in the test are not detected until after the test is finished. As a result, the internal state of the device at the point of error may not be determinable, requiring the simulation to be operated again in order to determine such internal states. This procedure consumes simulation cycles, and can require the expenditure of considerable time, especially during long tests.
A more useful and efficient type of testing is a dynamic testing environment. For this type of environment, a set of programming instructions is written to generate the test vectors in concurrence with the simulation of the model of the DUT and while potentially being controlled by the state feedback of the simulated device. This procedure enables directed random generation to be performed and to be sensitive to effects uncovered during the test itself on the state of the simulation model of the device. Thus, dynamic test generation clearly has many advantages for design verification.
Within the area of testing environments, both static and dynamic testing environments can be implemented only with fixed-vector or pre-generation input. However, a more powerful and more sophisticated implementation uses test generation to produce the environment. Such test generation involves the production of a random or pseudo-random testing environment, either through a custom generator program or else through a configurable generator. The custom generator program poses difficulties for reuse, in that it is typically designed for one specific hardware device as the DUT, and as such may be difficult or impossible to use for other devices.
Configurable generators can be further divided into two subcategories: template-based generators and constraint-based generators. Template-based generators for producing testing environments are domain specific, in the sense that they are only useful for certain types of hardware. If the device under test does not fit into the requirements of the template, then the template-based testing environment is not useful. For example, U.S. Pat. No. 5,202,889 discloses a process for generating biased pseudo-random test patterns for testing the design of an integrated circuit such as a microprocessor. However, as disclosed this process is heavily dependent upon the pre-defined templates produced for the particular architecture and function of the hardware, such as interactions with registers, and as such would be difficult to generalize to all types of test generation for different DUT""s. Furthermore, the disclosed process does not feature constraints or other relatively complex test generation expressions, further limiting the possible scope of the disclosed method for test generation.
Constraint-based generators, by contrast, are able to accommodate many different types of hardware, rather than hardware in a particular domain. One example of such a constraint-based test generation procedure is disclosed in U.S. patent application Ser. No. 09/020,792, filed on Feb. 6, 1998, incorporated by reference as if fully set forth herein. This test generation procedure interacts with, and sits as a higher level over, such hardware description languages as Verilog and VHDL. The test generation procedure is written in a hardware-oriented verification specific object-oriented programming language. This language is used to write various tests, which are then used to automatically create a device verification test by a test generator module. A wide variety of design environments can be tested and verified with this language. Thus, the disclosed procedure is generalizable, yet is also simple to program and to debug by the engineer.
The disclosed language features a number of elements such as structs for more richly and efficiently describing the design of the device to be simulated by the model. Structs are compound data structures. A struct definition is the basic data abstraction mechanism used to encapsulate data, data-relations and procedural activity in one single entity. A struct can therefore also be described as an object-oriented programming class. Each struct features one or more fields for storing data.
Among the disclosed features of the test generation procedure is the possibility to specify declarative relations between fields of a struct as constraints. Constraints are directives for the test generation. For example, type constraints are declared in the context of a struct, and are used to impose constraints on the values generated for the fields in a struct. A constraint can be used to restrict the possible values generated for fields in a particular run of a test. The restriction can narrow the choice to a single value, or to a range of possible values. Thus, the addition of constraints can direct and restrict the test generation procedure.
Unfortunately, as disclosed in U.S. patent application Ser. No. 09/020,792, these constraints are only operative according to the order of presentation, rather than according to any flexible, xe2x80x9clogicalxe2x80x9d order. Therefore, the disclosed constraints are rigid in nature, in the sense that altering the order of presentation of the constraints may change the outcome of applying these constraints, according to the disclosure of U.S. patent application Ser. No. 09/020,792. Thus, as disclosed, these constraints clearly have disadvantages.
A useful combination of these different types of testing environments would feature a flexible environment which is not domain specific, such that the environment would be suitable for many different types of hardware for the DUT. This flexible environment would feature dynamic test generation xe2x80x9con the flyxe2x80x9d, such that the environment would not be restricted to testing factors which were pre-computed or pre-generated. Finally, the test generation procedure for producing this testing environment would permit constraints to be applied according to the internal logical order, rather than according to the order of presentation, such that the order of presentation of the constraints does not necessarily determine the outcome of applying these constraints. Unfortunately, such test generation software for producing such a testing environment does not exist.
Therefore, there is an unmet need for, and it would be highly useful to have, a system and method for flexible constraints for test generation, such that constraints could be applied with a variety of different field structures on any level, including complex structures such as fields and lists, and such that the order of presentation of the constraints does not necessarily determine the outcome of applying such constraints, but rather that the constraints are applied according to an internal logical order.
The system and method of the present invention includes a simulation model with at least one flexible constraint on a data structure. The term xe2x80x9cflexible constraintxe2x80x9d indicates that the constraint is not limited to any one type of data structures, but instead can be used for any type of data structure. The preferred data structures include an object, a list of objects, a list of scalars and a mixture of at least two types of such structures. An object includes at least one data element and optionally includes a function for operating on the data element. The data element in turn could be a scalar or another object, for example. Preferably, the data structure is not a single scalar.
The method of the present invention determines each constraint, of a sequence of constraints, which should be applied to the data structure, and then applies the constraint during the test generation process. However, the constraint is preferably not applied according to the order of constraints in the sequence, but rather is applied according to an internal logical order of application. Since these constraints are effectively order-independent in terms of the order of presentation, each constraint is potentially bi-directional, in the sense that the definitions of the xe2x80x9cconstraint conditionxe2x80x9d and the xe2x80x9cdata structure to which the constraint should be appliedxe2x80x9d are flexible and can be reversed.
In order to apply these constraints according to the logical internal order, preferably the following steps are performed. First, each constraint of the sequence of constraints is defined. Next, a constraint is applied to a data structure for at least reducing the range of possible values, even the possible values are not restricted to one such value. This process is then repeated for other constraints in the sequence. The first constraint in the sequence (or at least an earlier constraint in the sequence) is then re-applied, in order to further restrict the range of possible values, and so forth. During this process, preferably the order of suitable application is also determined, such that a constraint which cannot be applied, for example because it requires values which have not yet been defined, is only applied after other constraint(s) which supply the missing values. The process is preferably repeated until no further restrictions can be placed on the range of potential values, more preferably until one such value is determined if possible.
According to the present invention, there is provided a method for test generation with a plurality of constraints on at least one data structure of a simulation model, the at least one data structure having at least one possible value, the steps of the method comprising: (a) analyzing the plurality of constraints to determine an internal logic order for a sequence of constraints, each of the plurality of constraints being of a form such that the at least one possible value is selected from a non-random set containing at least one value, the internal logic order being determined according to an ability to restrict a range of potential values for the non-random set for each of the plurality of constraints after applying a previous constraint in the sequence of constraints; (b) determining each of the plurality of constraints for the at least one data structure of the model according to the sequence of constraints; and (c) applying each of the plurality of constraints to the at least one data structure to perform the test generation.
Preferably, at least one constraint of the plurality of constraints is a flexible constraint. More preferably, the range of potential values includes a plurality of values. Alternatively and preferably, the at least one data structure of the model is an object including at least one data element and at least one function for operating on the at least one data element. More preferably, the object further includes at least one internal constraint being internal to the object for constraining the at least one data element of the object, and the step of applying the constraint to the object includes the steps of: (i) applying the at least one internal constraint to the at least one data element of the object; and (ii) applying the constraint to the at least one data element of the object, such that a non-random set of at least one value for the at least one data element of the object is first determined according to the internal constraint before being determined according to the constraint.
Preferably, the at least one data structure of the model is a list of a plurality of objects. More preferably, at least one of the plurality of objects in the list further includes at least one internal constraint being internal to the at least one of the plurality of objects for constraining the at least one data element of the at least one of the plurality of objects, and the step of applying the constraint to the list of the plurality of objects includes the steps of: (i) applying the at least one internal constraint to the at least one data element of the at least one of the plurality of objects; (ii) applying the constraint to the at least one data element of the at least one of the plurality of objects, such that if the internal constraint is present, a non-random set of at least one value for the at least one data element of the at least one of the plurality of objects is first determined according to the internal constraint before being determined according to the constraint; and (iii) repeating at least step (ii) for substantially all of the plurality of objects.
Preferably, the at least one data structure of the model is a list of a plurality of scalars. More preferably, the step of applying the constraint to the list of the plurality of scalars includes the step of sequentially applying the constraint to each of the plurality of scalars in the list.
Also preferably, the range of potential values includes a single value.
Preferably, the step of analyzing the plurality of constraints includes the step of identifying at least one of the plurality of constraints for being determined after at least one constraint is applied to the at least one data structure, such that at least a portion of the test generation is performed before the at least one constraint is determined.
Also preferably, the plurality of constraints are analyzed according to a presentation order, the presentation order being different from the internal logic order.
Hereinafter, the term xe2x80x9ccomputing platformxe2x80x9d refers to a particular computer hardware system or to a particular software operating system. Examples of such hardware systems include, but are not limited to, personal computers (PC), Macintosh(trademark) computers, mainframes, minicomputers and workstations. Examples of such software operating systems include, but are not limited to, UNIX, VMS, Linux, MacOS(trademark), DOS, FreeBSD, one of the Windows(trademark) operating systems by Microsoft Inc. (Seattle, Wash., USA), including Windows NT(trademark), Windows 3.x(trademark) (in which xe2x80x9cxxe2x80x9d is a version number, such as xe2x80x9cWindows 3.1(trademark)xe2x80x9d) and Windows95(trademark).
The method of the present invention could also be described as a plurality of instructions being performed by a data processor, such that the method of the present invention could be implemented as hardware, software, firmware or a combination thereof. For the present invention, a software application could be written in substantially any suitable programming language, which could easily be selected by one of ordinary skill in the art. The programming language chosen should be compatible with the computing platform according to which the software application is executed. Examples of suitable programming languages include, but are not limited to, C, C++ and Java.
Hereinafter, the term xe2x80x9cnon-randomxe2x80x9d refers to a process, or an entity selected by the process, which is not random but which is not necessarily deterministic.